<?php
/**
 * 树的排序和深度的计算
 * 树节点的结构 array('节点编号', '父节点编号', ... )
 * 
 * ============================================================================
 * 版权所有: (c) 2009-2011，<UEShop Inc>，并保留所有权利。
 * 网站地址: http://www.ueshop.cn
 * ----------------------------------------------------------------------------
 * 这不是一个自由软件！您只能在不用于商业目的的前提下对程序代码进行修改和使用；
 * 不允许对程序代码以任何形式任何目的的再发布。
 * ============================================================================
 *
 * @author      cmpan
 * @copyright   Copyright (c) 2009-2011 UEShop Inc. (http://www.ueshop.cn)
 * @license     http://www.ueshop.cn/1_0.txt
 */
class UE_Tree {
	/**
	 * 要处理的节点的数组
	 *
	 * @var array
	 */
	protected $_inNodes = array();
	
	protected $_icons = array(
	    0 => '',
	    1 => '　 |- ',
	    2 => '　 |　 |- ',
	    3 => '　 |　 |　 |- ',
	    4 => '　 |　 |　 |　 |- ',
	    5 => '　 |　 |　 |　 |　 |- ',
	    6 => '　 |　 |　 |　 |　 |　 |- ',
	    7 => '　 |　 |　 |　 |　 |　 |　 |- ',
	    8 => '　 |　 |　 |　 |　 |　 |　 |　 |- ',
	    9 => '　 |　 |　 |　 |　 |　 |　 |　 |　 |- ',
	);

	/**
	 * 处理后的节点的数组
	 *
	 * @var array
	 */
	protected $_outNodes = array();
	
	/**
	 * 节点的父节点的编号
	 *
	 * @var int
	 */
	protected $_nodeParentIdKey = 'reID';
	
	/**
	 * 节点的编号
	 *
	 * @var int
	 */
	protected $_nodeIdKey = 'id';
	
	/**
	 * 计算的复杂度
	 *
	 * @var int
	 */
	public static $step = 0;

	public function __construct() {}
	
	public function setParentNodeIdKey($key) {
		$this->_nodeParentIdKey = $key;
	}
	
	public function setNodeIdKey($key) {
		$this->_nodeIdKey = $key;
	}
	
	/**
	 * 填充要计算的数组
	 *
	 * @param array $var
	 * @param string $id
	 * @param string $parentId
	 */
	public function set($vars, $id = 'ID', $parentId = 'reID') {
		$this->_reset();
		if(!is_array($vars)) throw new Exception("错误的数据类型");
		foreach ($vars as $var) {
			$this->_inNodes[$var[$id]] = $var;
		}
		
		$this->_nodeIdKey = $id;
		$this->_nodeParentIdKey = $parentId;
	}
	
	private function _reset() {
		$this->_inNodes = array();
		$this->_outNodes = array();
		$this->step = 0;		
	}
	
	/**
	 * 添加节点
	 *
	 * @param array $node 节点
	 * @param string $key = null 节点的下标
	 */
	public function add($node, $key = null) {
		$node = $key ? array($key => $node) : array($node);
		$this->_inNodes = array_merge($this->_inNodes, $node);
	}

	/**
	 * 获取子节点,子节点将按父节点id和节点id来排序
	 *
	 * @param int $id 节点的id
	 * @param bool $isReturnSelf 是否返回自己
	 * @return array
	 */
	public function get($id = 0, $isReturnSelf = false) {
		if($id) {
			//print_r($this->_inNodes);
			if (isset($this->_inNodes[$id])) {
				if($id && $isReturnSelf) {
					$this->_outNodes[$this->_inNodes[$id][$this->_nodeIdKey]]           = $this->_inNodes[$id];
					$this->_outNodes[$this->_inNodes[$id][$this->_nodeIdKey]]['depth']  = 1;
					unset($this->_inNodes[$id]);
				}
			} else {
				//throw new Exception("错误的id");
				return array();
			}
		}
		$this->_analyze($id);
		$out = $this->_outNodes;
		$this->_outNodes = array();
		
		// 设置在该层是否是最后一个节点
		foreach ($out as $k=>$v) {			
			foreach ($out as $k2 => $v2) {
				if ($v2[$this->_nodeParentIdKey] == $v[$this->_nodeParentIdKey]) {
					$out[$k2]['isLastNode'] = false;
				}
			}
			
			$out[$k]['isLastNode'] = true;
		}
		
		//*
		// 设置icon
		foreach ($out as $kIcon => $vIcon) {
			if (!$vIcon['depth']) {
				continue;
			}
			$icon = $vIcon['isLastNode'] ? '　|__ ' : '　|-- ';
			
			if ($vIcon['depth'] == 1) {
				$picon = '';
			} else {
				if ($out[$vIcon[$this->_nodeParentIdKey]]['isLastNode']) {
					$picon = substr($out[$vIcon[$this->_nodeParentIdKey]]['icon'], 0, -4) . '　';
				} else {
					$picon = substr($out[$vIcon[$this->_nodeParentIdKey]]['icon'], 0, -4) . '| ';
				}
				
			}
			
			$out[$kIcon]['icon'] = $picon . $icon;
		}
		//*/
		return $out;
	}

	/**
	 * 分析节点
	 *
	 * @param int|string $id 节点id
	 */
	protected function _analyze($id) {
		foreach($this->_inNodes as $node) {
			$nodeId = $node[$this->_nodeIdKey];
			$nodeFid = $node[$this->_nodeParentIdKey];
			if(!isset($node['hasChile'])) $node['hasChile'] = false;
			self::$step ++ ;
			if($nodeFid == $id) {
				$this->_outNodes[$nodeId] = $node;
				
				if (!isset($this->_outNodes[$nodeFid]['depth'])) {
					$this->_outNodes[$nodeId]['depth'] = 0;
					$this->_outNodes[$nodeId]['isTop'] = true;
					$this->_outNodes[$nodeId]['icon']  = $this->_icons[0];
				} else {
					$this->_outNodes[$nodeId]['depth']      = $this->_outNodes[$nodeFid]['depth'] + 1;
					$this->_outNodes[$nodeId]['icon']       = $this->_icons[$this->_outNodes[$nodeId]['depth']];
					$this->_outNodes[$nodeFid]['hasChile']  = true;
					$this->_outNodes[$nodeId]['isTop']      = false;
				}
				
				$this->_outNodes[$nodeId]['chile'][] = $nodeId;
				$this->_outNodes[$nodeId]['chileId'] = $nodeId;
				
				// 把当前分类的id添加到父分类的chile
				$this->_addChileMark($nodeId, $nodeFid);
				
				$this->_analyze($nodeId);				
				//unset($this->_inNodes[$nodeId]);
			}
		}
	}
	
	public function __destruct() {
		unset($this->_inNodes);
		unset($this->_outNodes);
	}
	
	/**
	 * 获取节点的父节点
	 *
	 * @param int|string $id 节点id
	 */
	public function getReversed($id, $nodes = null) {
		if (!$nodes) {
			$nodes = $this->_outNodes;
		}
		
	    // 节点不存在择返回
	    if (empty($nodes[$id])) {
	    	return array();
	    }
		
	    $rNodes[] = $nodes[$id];
	    $revNodes = $this->getReversed($nodes[$id][$this->_nodeParentIdKey], $nodes);
	    if ($revNodes) {
	    	$rNodes = array_merge($revNodes, $rNodes);
	    }
	    
		return $rNodes;
	}
	
	/**
	 * 把当前分类的id加入父分类以及父分类的父分类的chile、chileId
	 *
	 * @param int $id
	 * @param int $fid
	 */
	private function _addChileMark($id, $fid) {
		if (empty($this->_outNodes[$id]) || empty($this->_outNodes[$fid]) || $this->_outNodes[$id]['isTop']) {
			return ;
		}
		
		$node = $this->_outNodes[$id];
		$fnode = &$this->_outNodes[$fid];
		
		// 当前分类id尚未添加到父分类则添加
		if ($node[$this->_nodeParentIdKey] == $fid) {			
			// 当前chile、chileId合并到父分类
		    $fnode['chile'] = array_merge($fnode['chile'], $node['chile']);
		    $fnode['chile'] = array_unique($fnode['chile']);
			$fnode['chileId'] = join(',', $fnode['chile']);
			
			$this->_addChileMark($fid, $fnode[$this->_nodeParentIdKey]);
		}
	}
}

